Fourier–Motzkin elimination

Fourier–Motzkin elimination, FME method, is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can look for both real and integer solutions. Its computational complexity is double-exponential.

Elimination (or ∃-elimination) of variables V from a system of relations (here, linear inequalities) consists in creating another system of the same kind, but without the variables V, such that both systems have the same solutions over the remaining variables.

If one eliminates all variables from a system of linear inequalities, then one obtains a system of constant inequalities, which can be trivially decided to be true or false, such that this system has solutions (is true) if and only if the original system has solutions. As a consequence, elimination of all variables can be used to detect whether a system of inequalities has solutions or not.

Let us consider a system $S$ of $n$ inequalities with $r$ variables $x_1$ to $x_r$ , with $x_r$ the variable to eliminate. The linear inequalities in the system can be grouped into three classes, depending on the sign (positive, negative or null) of the coefficient for $x_r$ :

those that are equivalent to some inequalities of the form $x_r \geq \sum_{k=1}^{r-1} a_k x_k$ ; let us note these as $x_r \geq A_i(x_1, \dots, x_{r-1})$ , for $i$ ranging from 1 to $n_A$ where $n_A$ is the number of such inequalities;
those that are equivalent to some inequalities of the form $x_r \leq \sum_{k=1}^{r-1} a_k x_k$ ; let us note these as $x_r \leq B_i(x_1, \dots, x_{r-1})$ , for $i$ ranging from 1 to $n_B$ where $n_B$ is the number of such inequalities;
those in which $x_r$ plays no role, grouped into a single conjunction $\phi$ .

The original system is thus equivalent to $\max(A_1(x_1, \dots, x_{r-1}), \dots, A_{n_A}(x_1, \dots, x_{r-1})) \leq x_r \leq \min(B_1(x_1, \dots, x_{r-1}), \dots, B_{n_B}(x_1, \dots, x_{r-1})) \wedge \phi$ .

Elimination consists in producing a system equivalent to $\exists x_r~S$ . Obviously, this formula is equivalent to $\max(A_1(x_1, \dots, x_{r-1}), \dots, A_{n_A}(x_1, \dots, x_{r-1})) \leq \min(B_1(x_1, \dots, x_{r-1}), \dots, B_{n_B}(x_1, \dots, x_{r-1})) \wedge \phi$ .

The inequality $\max(A_1(x_1, \dots, x_{r-1}), \dots, A_{n_A}(x_1, \dots, x_{r-1})) \leq \min(B_1(x_1, \dots, x_{r-1}), \dots, B_{n_B}(x_1, \dots, x_{r-1}))$ is equivalent to $n_A n_B$ inequalities $A_i(x_1, \dots, x_{r-1}) \leq B_j(x_1, \dots, x_{r-1})$ , for $1 \leq i \leq n_A$ and $1 \leq j \leq n_B$ .

We have therefore transformed the original system into another system where $x_r$ is eliminated. Note that the output system has $(n-n_A-n_B)%2Bn_A n_B$ inequalities. In particular, if $n_A = n_B = n/2$ , then the number of output inequalities is $n^2/4$ .

The operation is named after Joseph Fourier and Theodore Motzkin.

References

Schrijver, Alexander (1998). Theory of Linear and Integer Programming. John Wiley & sons. pp. 155–156. ISBN 0471982326.
Keßler, Christoph W.. "Parallel Fourier–Motzkin Elimination". Universität Trier. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.657&rep=rep1&type=pdf.
Williams, H. P. (1986). "Fourier's Method of Linear Programming and its Dual". American Mathematical Monthly 93: 681–695.

External links

Lectures on Convex Sets, notes by Niels Lauritzen, at Aarhus University, March 2010.

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear: Methods calling ...

... functions

Golden section search · Interpolation methods · Line search · Successive parabolic interpolation

... and gradients

Convergence	Trust region · Wolfe conditions

Quasi–Newton	BFGS and L-BFGS · DFP · Symmetric rank-one (SR1)

Other methods	Gauss–Newton · Gradient · Levenberg–Marquardt · Conjugate gradient

... and Hessians

Newton's method

Constrained nonlinear

General	Barrier methods · Penalty methods

Differentiable	Augmented Lagrangian methods · Sequential quadratic programming · Successive linear programming

Convex minimization

General

Interior point method · Reduced gradient (Frank–Wolfe) · Subgradient method · Cutting-plane method

Linear and
quadratic

Interior point	Ellipsoid method of Khachiyan · Projective algorithm of Karmarkar · Semidefinite programming

Basis-exchange	Simplex algorithm of Dantzig · Criss-cross algorithm · Principal pivoting algorithm of Lemke

Combinatorial

Paradigms

Approximation algorithm · Dynamic programming · Greedy algorithm · Integer programming (Branch & bound or cut)

Graph algorithms

Minimum spanning tree	Bellman–Ford algorithm · Borůvka · Dijkstra · Floyd–Warshall · Johnson · Kruskal

Network flows

Dinic · Edmonds–Karp · Ford–Fulkerson · Push-relabel maximum flow

Metaheuristics

Evolutionary algorithm · Hill climbing · Local search · Simulated annealing · Tabu search

Categories (Algorithms · Methods · Heuristics) · Software

‹The stub template below has been proposed for renaming to . See stub types for deletion to help reach a consensus on what to do.
Feel free to edit the template, but the template must not be blanked, and this notice must not be removed, until the discussion is closed. For more information, read the guide to deletion.›

Fourier–Motzkin elimination

See also

References

External links